SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Pseudo-Boolean function</title>

</head>

Pseudo-Boolean function

</h1>

</header>

In <a href="Mathematics" title="Mathematics">mathematics</a> and <a href="Optimization" class="mw-redirect" title="Optimization">optimization</a>, a pseudo-Boolean function is a <a href="Function_(mathematics)" title="Function (mathematics)">function</a> of the form

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f:\mathbf {B} ^{n}\to \mathbb {R} ,}</annotation>

</semantics>

</math><img src="./36db543fb979b9b26fc32195110ed6255f40f403.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.274ex; height:2.676ex;" alt="{\displaystyle f:\mathbf {B} ^{n}\to \mathbb {R} ,}" loading="lazy"></dd></dl>

where B = {0, 1} is a <a href="Boolean_domain" title="Boolean domain">Boolean domain</a> and n is a nonnegative <a href="Integer" title="Integer">integer</a> called the <a href="Arity" title="Arity">arity</a> of the function. A <a href="Boolean_function" title="Boolean function">Boolean function</a> is then a special case, where the values are also restricted to 0 or 1.

<div class="mw-heading mw-heading2"><h2 id="Representations">Representations</h2></div>

Any pseudo-Boolean function can be written uniquely as a <a href="Multi-linear" class="mw-redirect" title="Multi-linear">multi-linear</a> polynomial:<a href="#cite_note-1">[1]</a><a href="#cite_note-2">[2]</a>

</mrow>

</mrow>

</munder>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f({\boldsymbol {x}})=a+\sum _{i}a_{i}x_{i}+\sum _{i<j}a_{ij}x_{i}x_{j}+\sum _{i<j<k}a_{ijk}x_{i}x_{j}x_{k}+\ldots }</annotation>

</semantics>

</math><img src="./f59820caab3481d5fa56f85a637e3c96dd2d696a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:57.148ex; height:5.843ex;" alt="{\displaystyle f({\boldsymbol {x}})=a+\sum _{i}a_{i}x_{i}+\sum _{i<j}a_{ij}x_{i}x_{j}+\sum _{i<j<k}a_{ijk}x_{i}x_{j}x_{k}+\ldots }" loading="lazy"></dd></dl>

The degree of the pseudo-Boolean function is simply the degree of the <a href="Polynomial" title="Polynomial">polynomial</a> in this representation.

In many settings (e.g., in <a href="Analysis_of_Boolean_functions" title="Analysis of Boolean functions">Fourier analysis of pseudo-Boolean functions</a>), a pseudo-Boolean function is viewed as a function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> that maps <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{-1,1\}^{n}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{-1,1\}^{n}}</annotation>

</semantics>

</math><img src="./a13b108ff602485218e0768ca581104b3fd992e8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.71ex; height:2.843ex;" alt="{\displaystyle \{-1,1\}^{n}}" loading="lazy"> to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {R} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {R} }</annotation>

</semantics>

</math><img src="./786849c765da7a84dbc3cce43e96aad58a5868dc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \mathbb {R} }" loading="lazy">. Again in this case we can uniquely write <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> as a multi-linear polynomial:

</mrow>

</munder>

<mover>

</mover>

</mrow>

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x)=\sum _{I\subseteq [n]}{\hat {f}}(I)\prod _{i\in I}x_{i},}</annotation>

</semantics>

</math><img src="./67a7bdd3733f808c1afd39a73a728606c2124068.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.505ex; width:23.111ex; height:6.009ex;" alt="{\displaystyle f(x)=\sum _{I\subseteq [n]}{\hat {f}}(I)\prod _{i\in I}x_{i},}" loading="lazy"> where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\hat {f}}(I)}">

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\hat {f}}(I)}</annotation>

</semantics>

</math><img src="./d87cce31c19c40b1cb0a875801e96432463d6c6e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.68ex; height:3.343ex;" alt="{\displaystyle {\hat {f}}(I)}" loading="lazy"> are Fourier coefficients of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [n]=\{1,...,n\}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [n]=\{1,...,n\}}</annotation>

</semantics>

</math><img src="./a4b11a82ea9a25f993c8bd1d08541c97c01efae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.839ex; height:2.843ex;" alt="{\displaystyle [n]=\{1,...,n\}}" loading="lazy">.

<div class="mw-heading mw-heading2"><h2 id="Optimization">Optimization</h2></div>

Minimizing (or, equivalently, maximizing) a pseudo-Boolean function is <a href="NP-hard" class="mw-redirect" title="NP-hard">NP-hard</a>. This can easily be seen by formulating, for example, the <a href="Maximum_cut" title="Maximum cut">maximum cut</a> problem as maximizing a pseudo-Boolean function.<a href="#cite_note-Boros2002-3">[3]</a>

<div class="mw-heading mw-heading3"><h3 id="Submodularity">Submodularity</h3></div>

The <a href="Submodular_set_function" title="Submodular set function">submodular set functions</a> can be viewed as a special class of pseudo-Boolean functions, which is equivalent to the condition

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f({\boldsymbol {x}})+f({\boldsymbol {y}})\geq f({\boldsymbol {x}}\wedge {\boldsymbol {y}})+f({\boldsymbol {x}}\vee {\boldsymbol {y}}),\;\forall {\boldsymbol {x}},{\boldsymbol {y}}\in \mathbf {B} ^{n}\,.}</annotation>

</semantics>

</math><img src="./60809caebfc60becc4d03ab904d63b4ebd9193c5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:48.909ex; height:2.843ex;" alt="{\displaystyle f({\boldsymbol {x}})+f({\boldsymbol {y}})\geq f({\boldsymbol {x}}\wedge {\boldsymbol {y}})+f({\boldsymbol {x}}\vee {\boldsymbol {y}}),\;\forall {\boldsymbol {x}},{\boldsymbol {y}}\in \mathbf {B} ^{n}\,.}" loading="lazy"></dd></dl>

This is an important class of pseudo-boolean functions, because they can be <a href="Submodular_set_function#Submodular_set_function_minimization" title="Submodular set function">minimized in polynomial time</a>. Note that minimization of a submodular function is a polynomially solvable problem independent on the presentation form, for e.g. pesudo-Boolean polynomials, opposite to maximization of a submodular function which is NP-hard, Alexander Schrijver (2000).

<div class="mw-heading mw-heading3"><h3 id="Roof_Duality">Roof Duality</h3></div>

If f is a quadratic polynomial, a concept called roof duality can be used to obtain a lower bound for its minimum value.<a href="#cite_note-Boros2002-3">[3]</a> Roof duality may also provide a partial assignment of the variables, indicating some of the values of a minimizer to the polynomial. Several different methods of obtaining lower bounds were developed only to later be shown to be equivalent to what is now called roof duality.<a href="#cite_note-Boros2002-3">[3]</a>

<div class="mw-heading mw-heading3"><h3 id="Quadratizations">Quadratizations</h3></div>

If the degree of f is greater than 2, one can always employ reductions to obtain an equivalent quadratic problem with additional variables. One possible reduction is

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \displaystyle -x_{1}x_{2}x_{3}=\min _{z\in \mathbf {B} }z(2-x_{1}-x_{2}-x_{3})}</annotation>

</semantics>

</math><img src="./97ba035787969083ac7a28f29a2f4bb4de81c77e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:36.054ex; height:4.009ex;" alt="{\displaystyle \displaystyle -x_{1}x_{2}x_{3}=\min _{z\in \mathbf {B} }z(2-x_{1}-x_{2}-x_{3})}" loading="lazy"></dd></dl>

There are other possibilities, for example,

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \displaystyle -x_{1}x_{2}x_{3}=\min _{z\in \mathbf {B} }z(-x_{1}+x_{2}+x_{3})-x_{1}x_{2}-x_{1}x_{3}+x_{1}.}</annotation>

</semantics>

</math><img src="./b8d6e6cacc8a021e33775024852873d5a7554b11.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:54.946ex; height:4.009ex;" alt="{\displaystyle \displaystyle -x_{1}x_{2}x_{3}=\min _{z\in \mathbf {B} }z(-x_{1}+x_{2}+x_{3})-x_{1}x_{2}-x_{1}x_{3}+x_{1}.}" loading="lazy"></dd></dl>

Different reductions lead to different results. Take for example the following <a href="Cubic_function" title="Cubic function">cubic polynomial</a>:<a href="#cite_note-Kahl2011-4">[4]</a>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \displaystyle f({\boldsymbol {x}})=-2x_{1}+x_{2}-x_{3}+4x_{1}x_{2}+4x_{1}x_{3}-2x_{2}x_{3}-2x_{1}x_{2}x_{3}.}</annotation>

</semantics>

</math><img src="./1eb3d43258427bbf7dcebe4e5e62008683c171a6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:61.635ex; height:2.843ex;" alt="{\displaystyle \displaystyle f({\boldsymbol {x}})=-2x_{1}+x_{2}-x_{3}+4x_{1}x_{2}+4x_{1}x_{3}-2x_{2}x_{3}-2x_{1}x_{2}x_{3}.}" loading="lazy"></dd></dl>

Using the first reduction followed by roof duality, we obtain a lower bound of −3 and no indication on how to assign the three variables. Using the second reduction, we obtain the (tight) lower bound of −2 and the optimal assignment of every variable (which is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {(0,1,1)}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {(0,1,1)}}</annotation>

</semantics>

</math><img src="./8a93a4dc4b96317adc8dc14b7277135eeae94f1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.365ex; height:2.843ex;" alt="{\displaystyle {(0,1,1)}}" loading="lazy">).

<div class="mw-heading mw-heading3"><h3 id="Polynomial_Compression_Algorithms">Polynomial Compression Algorithms</h3></div>

Consider a pseudo-Boolean function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> as a mapping from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{-1,1\}^{n}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{-1,1\}^{n}}</annotation>

</semantics>

</math><img src="./a13b108ff602485218e0768ca581104b3fd992e8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.71ex; height:2.843ex;" alt="{\displaystyle \{-1,1\}^{n}}" loading="lazy"> to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {R} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {R} }</annotation>

</semantics>

</math><img src="./786849c765da7a84dbc3cce43e96aad58a5868dc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \mathbb {R} }" loading="lazy">. Then <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x)=\sum _{I\subseteq [n]}{\hat {f}}(I)\prod _{i\in I}x_{i}.}">

</mrow>

</munder>

<mover>

</mover>

</mrow>

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x)=\sum _{I\subseteq [n]}{\hat {f}}(I)\prod _{i\in I}x_{i}.}</annotation>

</semantics>

</math><img src="./22609c89d035ac0f30c469faed7cb8bfecdd362a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.505ex; width:23.111ex; height:6.009ex;" alt="{\displaystyle f(x)=\sum _{I\subseteq [n]}{\hat {f}}(I)\prod _{i\in I}x_{i}.}" loading="lazy"> Assume that each coefficient <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\hat {f}}(I)}">

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\hat {f}}(I)}</annotation>

</semantics>

</math><img src="./d87cce31c19c40b1cb0a875801e96432463d6c6e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.68ex; height:3.343ex;" alt="{\displaystyle {\hat {f}}(I)}" loading="lazy"> is integral. Then for an integer <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> the problem P of deciding whether <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x)}</annotation>

</semantics>

</math><img src="./202945cce41ecebb6f643f31d119c514bec7a074.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.418ex; height:2.843ex;" alt="{\displaystyle f(x)}" loading="lazy"> is more or equal to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> is NP-complete. It is proved in <a href="#cite_note-Crowston2011-5">[5]</a> that in polynomial time we can either solve P or reduce the number of variables to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(k^{2}\log k).}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(k^{2}\log k).}</annotation>

</semantics>

</math><img src="./0bf3a3e551292e94e255c11027d5aada60fa649c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.452ex; height:3.176ex;" alt="{\displaystyle O(k^{2}\log k).}" loading="lazy"> Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r}</annotation>

</semantics>

</math><img src="./0d1ecb613aa2984f0576f70f86650b7c2a132538.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:1.676ex;" alt="{\displaystyle r}" loading="lazy"> be the degree of the above multi-linear polynomial for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy">. Then <a href="#cite_note-Crowston2011-5">[5]</a> proved that in polynomial time we can either solve P or reduce the number of variables to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r(k-1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r(k-1)}</annotation>

</semantics>

</math><img src="./f2ccf165f8a0104c2efda9f477d96560b7aae01f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.072ex; height:2.843ex;" alt="{\displaystyle r(k-1)}" loading="lazy">.

<ul><li><a href="Boolean_function" title="Boolean function">Boolean function</a></li>

<li><a href="Quadratic_pseudo-Boolean_optimization" title="Quadratic pseudo-Boolean optimization">Quadratic pseudo-Boolean optimization</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFHammerRosenbergRudeanu1963" class="citation journal cs1 cs1-prop-foreign-lang-source">Hammer, P.L.; Rosenberg, I.; Rudeanu, S. (1963). "On the determination of the minima of pseudo-Boolean functions". Studii și cercetări matematice (in Romanian) (14): 359–364. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0039-4068">0039-4068</a>.</cite>

</li>

<li id="cite_note-2"><a href="#cite_ref-2">^</a> <cite id="CITEREFHammerRudeanu1968" class="citation book cs1">Hammer, Peter L.; Rudeanu, Sergiu (1968). Boolean Methods in Operations Research and Related Areas. Springer. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-642-85825-3</bdi>.</cite>

</li>

<li id="cite_note-Boros2002-3">^ <a href="#cite_ref-Boros2002_3-0">a</a> <a href="#cite_ref-Boros2002_3-1">b</a> <a href="#cite_ref-Boros2002_3-2">c</a> <cite id="CITEREFBorosHammer2002" class="citation journal cs1">Boros, E.; Hammer, P. L. (2002). <a rel="nofollow" class="external text" href="http://orbi.ulg.ac.be/handle/2268/202427">"Pseudo-Boolean Optimization"</a>. <a href="Discrete_Applied_Mathematics" title="Discrete Applied Mathematics">Discrete Applied Mathematics</a>. 123 (1–3): 155–225. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0166-218X%2801%2900341-9">10.1016/S0166-218X(01)00341-9</a>. <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<a rel="nofollow" class="external text" href="https://hdl.handle.net/2268%2F202427">2268/202427</a>.</cite>

</li>

<li id="cite_note-Kahl2011-4"><a href="#cite_ref-Kahl2011_4-0">^</a> <cite id="CITEREFKahlStrandmark2011" class="citation conference cs1">Kahl, F.; Strandmark, P. (2011). <a rel="nofollow" class="external text" href="http://www.maths.lth.se/vision/publdb/reports/pdf/kahl-strandmark-iccv-11.pdf">Generalized Roof Duality for Pseudo-Boolean Optimization</a> (PDF). <a href="International_Conference_on_Computer_Vision" title="International Conference on Computer Vision">International Conference on Computer Vision</a>.</cite>

</li>

<li id="cite_note-Crowston2011-5">^ <a href="#cite_ref-Crowston2011_5-0">a</a> <a href="#cite_ref-Crowston2011_5-1">b</a> <cite id="CITEREFCrowstonFellowsGutinJones2011" class="citation journal cs1">Crowston, R.; Fellows, M.; Gutin, G.; Jones, M.; Rosamond, F.; Thomasse, S.; Yeo, A. (2011). "Simultaneously Satisfying Linear Equations Over GF(2): MaxLin2 and Max-r-Lin2 Parameterized Above Average". Proc. Of FSTTCS 2011. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1104.1135">1104.1135</a>. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2011arXiv1104.1135C">2011arXiv1104.1135C</a>.</cite>

</li>

</ol></div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

<ul><li><cite id="CITEREFIshikawa2011" class="citation journal cs1">Ishikawa, H. (2011). "Transformation of general binary MRF minimization to the first order case". <a href="IEEE_Transactions_on_Pattern_Analysis_and_Machine_Intelligence" title="IEEE Transactions on Pattern Analysis and Machine Intelligence">IEEE Transactions on Pattern Analysis and Machine Intelligence</a>. 33 (6): 1234–1249. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.675.2183">10.1.1.675.2183</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2Ftpami.2010.91">10.1109/tpami.2010.91</a>. <a href="PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/20421673">20421673</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:17314555">17314555</a>.</cite></li>

<li><cite id="CITEREFO'Donnell2008" class="citation journal cs1"><a href="Ryan_O'Donnell_(computer_scientist)" title="Ryan O'Donnell (computer scientist)">O'Donnell, Ryan</a> (2008). <a rel="nofollow" class="external text" href="https://eccc.weizmann.ac.il/report/2008/055/">"Some topics in analysis of Boolean functions"</a>. ECCC. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1433-8092">1433-8092</a>.</cite></li>

<li><cite id="CITEREFRotherKolmogorovLempitskySzummer2007" class="citation conference cs1">Rother, C.; Kolmogorov, V.; Lempitsky, V.; Szummer, M. (2007). <a rel="nofollow" class="external text" href="http://research.microsoft.com/pubs/67978/cvpr07-QPBOpi.pdf">Optimizing Binary MRFs via Extended Roof Duality</a> (PDF). <a href="Conference_on_Computer_Vision_and_Pattern_Recognition" title="Conference on Computer Vision and Pattern Recognition">Conference on Computer Vision and Pattern Recognition</a>.</cite></li>

<li><cite id="CITEREFSchrijver2000" class="citation journal cs1">Schrijver, Alexander (November 2000). <a rel="nofollow" class="external text" href="https://doi.org/10.1006%2Fjctb.2000.1989">"A Combinatorial Algorithm Minimizing Submodular Functions in Strongly Polynomial Time"</a>. Journal of Combinatorial Theory. 80 (2): 346–355. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1006%2Fjctb.2000.1989">10.1006/jctb.2000.1989</a>.</cite></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-06-21" href="https://en.wikipedia.org/wiki/?title=Pseudo-Boolean_function&oldid=1296620603">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>